package cn.arnold.search;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {
        int[] array1 = {1, 8, 10, 89, 1000, 1234};
        int[] array2 = {1, 8, 10, 8, 8, 89, 1000, 1234, 8};
        int i = searchOne(array1, 0, array1.length - 1, 8);
        System.out.println(i);
        List<Integer> list = searchAll(array2, 0, array2.length - 1, 8);
        System.out.println(list);
    }

    /**
     * 查找到一个匹配的后就退出
     *
     * @param array
     * @param left      待查找数组的最左边索引
     * @param right     待查找数组的最右边索引
     * @param findValue
     * @return
     */
    public static int searchOne(int[] array, int left, int right, int findValue) {

        int mid = (left + right) / 2;   // 中间索引
        int midValue = array[mid];
        // 退出查找条件:
        // 1. 查找完所有，没有匹配：left>right
        // 2. 待查找元素越界：findValue<array[left] || findValue>array[right]
        if (left > right || findValue < array[left] || findValue > array[right]) {
            return -1;
        }
        // findValue>midValue则在右边递归查找
        // findValue<midValue则在左边递归查找
        // findValue=midValue则返回mid
        if (findValue > midValue) {
            return searchOne(array, mid + 1, right, findValue);
        } else if (findValue < midValue) {
            return searchOne(array, left, mid - 1, findValue);
        } else {
            return mid;
        }
    }

    public static List<Integer> searchAll(int[] array, int left, int right, int findValue) {

        int mid = (left + right) / 2;   // 中间索引
        int midValue = array[mid];

        if (left > right || findValue < array[left] || findValue > array[right]) {
            return new ArrayList<Integer>();
        }

        if (findValue > midValue) {
            return searchAll(array, mid + 1, right, findValue);
        } else if (findValue < midValue) {
            return searchAll(array, left, mid - 1, findValue);
        } else {
            // 1. 找到mid后，不要马上返回
            // 2. 向mid索引值左边扫描，将所有匹配的下标添加到list
            // 3. 向mid索引值右边扫描，将所有匹配的下标添加到list
            List resList = new ArrayList<Integer>();
            // 将匹配到的第一个下标添加到list
            resList.add(mid);
            // 向左扫描
            int tempIndex = mid - 1;
            while (tempIndex > 0) {
                if (findValue == array[tempIndex]) {
                    resList.add(tempIndex);
                }
                tempIndex--;

            }
            // 向右扫描
            tempIndex = mid + 1;
            while (tempIndex < array.length) {
                if (findValue == array[tempIndex]) {
                    resList.add(tempIndex);
                }
                tempIndex++;

            }
            return resList;
        }
    }
}
